/*
实验5-2 树的宽度
分数 25
作者 陈越
单位 浙江大学

二叉树的宽度是指各层结点数的最大值。本题就要求根据层序序列计算给定二叉树的宽度。
函数接口定义：

int Width(TElemSet levelorder[], int n);

其中 TElemSet 定义为 int 型；树中所有元素键值为正整数；层序序列数组 levelorder 中用 -1 表示空；n 是数组中元素个数。函数 Width 需要返回树的宽度值。空树的宽度为 0。

输入样例：

9
1 2 3 -1 4 -1 -1 -1 -1

输出样例：

2
*/

#include <stdio.h>
#include <stdlib.h>

typedef int TElemSet;
#define NIL -1 /* 假设数据为为正整数，NIL定义为非法数据，表示空 */

int Width(TElemSet levelorder[], int n);

int main(void)
{
    TElemSet *levelorder;
    int n, i;
    
    scanf("%d\n", &n);
    levelorder = (TElemSet *)malloc(sizeof(TElemSet) * n);
    for (i=0; i<n; i++) {
        scanf("%d", &levelorder[i]);
    }
    printf("%d\n", Width(levelorder, n));
     
    return 0;
}
/* 你的代码将被嵌在这里 */

int Width(TElemSet levelorder[], int n) {
    if (n == 0) return 0; // 空树宽度为 0

    int max_width = 0; // 记录最大宽度
    int current_width = 0; // 当前层的宽度
    int level_start = 0; // 当前层的起始位置
    int level_end = 1; // 当前层的结束位置

    while (level_start < n) {
        current_width = 0;
        for (int i = level_start; i < level_end; i++) {
            if (levelorder[i] != NIL) {
                current_width++; // 统计当前层的非空节点数
            }
        }
        if (current_width > max_width) {
            max_width = current_width; // 更新最大宽度
        }
        level_start = level_end; // 移动到下一层的起始位置
        level_end = 2 * level_end + 1; // 更新下一层的结束位置
        if (level_end > n) {
            level_end = n; // 防止越界
        }
    }

    return max_width;
}